package com.jlh.viewer.algorithm;

/**
 * com.jlh.viewer.algorithm
 * Created by ASUS on 2017/4/19.
 * 21:25
 */
public class LineTree {
    int[] tree;
    int size;
    public LineTree(int n){
        tree= new int[n*4+1];
        size=n;
    }
    public void update (int n,int value){
        update(1,1,size,n,value);
    }
    private int update (int index,int left,int right,int n,int value){
        if (left==right){
            tree[index]=value;
            return value;
        }else {
            int mid = (left+right)/2;
            if (mid>=n)
                tree[index]=Math.max(update(index*2,left,mid,n,value),tree[index*2+1]);
            else
                tree[index]=Math.max(update(index*2+1,mid+1,right,n,value),tree[index*2]);
        }
        return tree[index];
    }

    public int query (int start,int end){
        return query(1,1,size,start,end);
    }
    private int query (int index,int left,int right,int start,int end){
        if (left>=start&&right<=end)
            return tree[index];
        int mid = (left+right)/2;
        int a = 0,b=0;
        if (start<=mid)
            a=query(index*2,left,mid,start,end);
        if (end>mid)
            b=query(index*2+1,mid+1,right,start,end);

        return Math.max(a,b);
    }
}
